public class Solution1588 {
    public int sumOddLengthSubarrays(int[] arr) {
        int res = 0;
        int[] prefixSum = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            if(i == 0){
                prefixSum[i] = arr[i];
            }
            else{
                prefixSum[i] = arr[i] + prefixSum[i-1];
            }
        }
        for (int i = 1; i <= arr.length; i+=2) {
            int path = i-1;
            for (int left = 0; left <= arr.length-i; left++) {
                int right = left + path;
                res += prefixSum[right] - (left == 0? 0:prefixSum[left-1]);
            }
        }
        return res;
    }
}
